package com.dmall.chapter09.section05;

import com.dmall.chapter02.section09.Graph;
import com.dmall.chapter09.section03.HamiltonLoop3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈密尔顿路径算法
 * @author wx
 * @date 2020-03-16 22:29:35
 */
public class HamiltonPath {
    private Graph G;
    private boolean[] visited;
    private int[] pre;
    private int end;
    private int start;

    public HamiltonPath(Graph G, int start) {
        this.G = G;
        this.visited = new boolean[G.V()];
        this.pre = new int[G.V()];
        this.start = start;
        this.end = -1;
        dfs(start, start, G.V());
    }

    private boolean dfs(int v, int parent, int left) {
        visited[v] = true;
        pre[v] = parent;
        left --;
        if (left == 0) {
            end = v;
            return true;
        }
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                if (dfs(w, v, left)) {
                    return true;
                }
            }
        }
        visited[v] = false;
        return false;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (end == -1) {
            return res;
        }
        int cur = end;
        while (cur != start) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(start);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        String filename = HamiltonPath.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename);
        HamiltonPath hp = new HamiltonPath(g, 0);
        System.out.println(hp.result());

        String filename2 = HamiltonPath.class.getClassLoader().getResource("g2.txt").getPath();
        Graph g2 = new Graph(filename2);
        HamiltonPath hp2 = new HamiltonPath(g2, 1);
        System.out.println(hp2.result());

        String filename3 = HamiltonPath.class.getClassLoader().getResource("g3.txt").getPath();
        Graph g3 = new Graph(filename3);
        HamiltonPath hp3 = new HamiltonPath(g3, 0);
        System.out.println(hp3.result());

        HamiltonPath hp4 = new HamiltonPath(g3, 1);
        System.out.println(hp4.result());
    }
}
